/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the SaverioMiroddiSoftware nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * AbstractNode.java
 * ---------------------------
 *
 */
package btree;

import java.util.Iterator;
import java.util.List;

import btree.BTree.AdditionReturn;
import btree.BTree.DeletionReturn;

/**
 * Generic interface for a B-Tree node.
 * 
 * @author Saverio Miroddi
 */
@SuppressWarnings("unchecked")
public abstract class AbstractNode 
{
	// FIXME: parameterize min elems
	/** Must be less than half, otherwise merging spectacularly explodes */
	protected static final int MIN_ELEMS = 1;
	
	protected static final AbstractNode NULL_NODE = null;
	/** DO NOT CHANGE */
	protected static final int POSITION_GREATEST = Integer.MIN_VALUE;

	protected int _currentElems;
	protected AbstractNode _rightPtr;
	
	protected AbstractNode()
	{
		_currentElems = 0; // optional

		_number = _counter++;
	}
	
	protected void fixedInsert(
		AbstractElement element, int position)
	{
		System.arraycopy(getElementsPtr(), position, 
						 getElementsPtr(), position + 1,
						 _currentElems - position);
		getElementsPtr()[position] = element;
		_currentElems++;
	}
	
	/**
	 * Insert in the appropriate position mantaining the natural order of the
	 * elements.<br>
	 * <b>HIGHLY COUPLED:</b> modifies _elements and _currentElems.
	 * <p>
	 */
	protected void orderedInsert(
			AbstractElement inserting)
	{
		_currentElems = orderedInsertInArray(getElementsPtr(), _currentElems, inserting);
	}

	protected static int orderedInsertInArray(
			AbstractElement[] elements, int currentElems, 
			AbstractElement inserting)
	{
		assert(currentElems < elements.length);
		
		int insertPos = findPositionInArray(elements, currentElems, inserting.value);
		
		if (insertPos != POSITION_GREATEST) {
			if (insertPos < 0) insertPos = -(insertPos + 1); // inexact position
			
			// the arraycopy working is compatible with this type of copy!
			System.arraycopy(elements, insertPos, elements, insertPos + 1, 
							 currentElems - insertPos);
			elements[insertPos] = inserting;
		}
		else {
			// if we are here, it means it is the greatest
			elements[currentElems] = inserting;
		}
		
		currentElems++;
		return currentElems;
	}
	
	/**
	 * <b>HIGHLY COUPLED:</b> modifies _elements and _currentElems.
	 */
	protected AbstractElement removeElement(int pos)
	{
		AbstractElement[] elements = getElementsPtr();
		AbstractElement removed = elements[pos];
		
		System.arraycopy(elements, pos + 1, elements, pos, _currentElems - 1 - pos);
		elements[_currentElems - 1] = null;
		_currentElems--;
		
		return removed;
	}
	
	/**
	 * Works exactly as Arrays.binarysearch(); except that the return value when
	 * not found (that is, when value is greatest than all the elements) is
	 * POSITION_GREATEST.<br>
	 * It is possible to look for a positive exact match verifying if the result
	 * is &#062;= 0.<br>
	 * Use pos = -(pos + 1) to normalize.
	 * 
	 * @see java.util.Arrays#binarySearch(Object[], Object)
	 */
	protected int findPosition(Comparable value)
	{
		return findPositionInArray(getElementsPtr(), _currentElems, value);
	}

	/**
	 * Perform a binary search.<br>
	 * This is a slightly modified version of JDK routine; it's terribly
	 * similar, but there is only one possible way of writing it [iteratively].
	 */
	protected static int findPositionInArray(
			AbstractElement[] elements, int currentElems, Comparable value)
	{
		int left = 0;
		int right = currentElems - 1;

		while (left <= right) {
		    int middle = (left + right) / 2; // unopt
		    Comparable middleValue = elements[middle].value;
		    int compare = middleValue.compareTo(value);

		    if (compare < 0) left = middle + 1;
		    else if (compare > 0) right = middle - 1;
		    else return middle;
		}

		if (left >= currentElems) return POSITION_GREATEST;
		else return -(left + 1);
	}
	
	protected boolean hasMinimum()
	{
		return (_currentElems >= MIN_ELEMS);
	}
	
	protected boolean hasMinimumPlusOne()
	{
		return (_currentElems >= MIN_ELEMS + 1);
	}
	
	///////////////////////////////////////////////////////////////////////////
	// ABSTRACT METHODS
	///////////////////////////////////////////////////////////////////////////
	
	/**
	 * Go all the way until leaf and insert into the leaf.
	 * 
	 * @param childPtr
	 *            this is the current node pointer to the child where the node
	 *            is being inserted.<br>
	 *            if splitHappens, the appropriate pointer is changed to point
	 *            to the new (right) node. because of d*mn lack of pass-by-ref
	 *            we must use this orrible "thing".<br>
	 *            0-based; if exceeds the number of elements, it represents
	 *            'rightPtr'.
	 * @return if splitHappens, the returning node is the one popped.
	 */
	public abstract AdditionReturn add(
			RecElement recElement);
	
	/**
	 * Return the value associated to the specified value (which will be found
	 * in a leaf node).
	 * 
	 * @return value found; SEARCH_VAL_NOT_FOUND if value is not found.
	 */
	public abstract long search(
			Comparable<?> value);
	
	/**
	 * Return an iterator for all the values of the tree.
	 */
	public abstract Iterator<Long> orderedTraversal();
	
	/**
	 * Remove an element.
	 * <p>
	 * The callee must pass the node pointers at the left and right of the path node.<br>
	 * If there is no right or left (because the value is at the border of the node), null
	 * is passed.<br>
	 * The pointers must be renewed for every call (that is, for every level).
	 * 
	 * @return the new rightmost element of the node which contained the deleted
	 *         element. return null if the element hasn't been found.
	 */
	public abstract DeletionReturn remove(
			Comparable<?> value, 
			AbstractNode leftSibling, AbstractNode rightSibling);

	protected abstract AbstractElement[] getElementsPtr();
	
	/**
	 * Internal nodes recursively call on rightPtr; children return the
	 * rightmost value.
	 */
	protected abstract Comparable getSubtreeRightmostVal();
	
	///////////////////////////////////////////////////////////////////////////
	// SUPPORT/DEBUG METHODS
	///////////////////////////////////////////////////////////////////////////
	
	private static int _counter = 0;
	private final int _number;
	
	@Override
	public String toString() {
		String result = "";

		if (BTree.FULL_DEBUG) {
			result += "{" + _number + " C" + _currentElems + "}";
		}
		
		for (AbstractElement element : getElementsPtr())
			result += " " + ((element == null) ? ("*") : (element)) ;

		if (BTree.FULL_DEBUG) {
			result += " [" + (_rightPtr == AbstractNode.NULL_NODE ? "*" : _rightPtr._number) + "]";
		}
		
		return result;
	}

	public int getNumber()
	{
		return _number;
	}
	
	public AbstractNode getRightPtr()
	{
		return _rightPtr;
	}
	
	@Override
	public boolean equals(Object other) {
		return (other instanceof AbstractNode) && 
			   (_number == ((AbstractNode)other)._number);
	}

	/** Must not return null or null children. */
	public abstract List<? extends AbstractNode> getChildren();
}